Dénombrement (Counting)consiste à « compter le nombre total de cas possibles selon un plan donné ». Il constitue la base des mathématiques combinatoires, visant à décomposer logiquement des événements complexes en opérations locales simples, disjointes ou ordonnées.
Imaginez que vous devez entrer dans une cour :
1. Addition par catégories (en parallèle): Il y a $m$ portes à gauche et $n$ portes à droite. Vous n’avez qu’à en choisir une pour entrer. Nombre de méthodes : $m+n$.
2. Multiplication par étapes (en série): Vous devez traverser deux murs. Le premier mur comporte $m$ portes, le deuxième $n$ portes. Vous devez franchir les deux étapes consécutivement. Nombre de méthodes : $m \times n$.
Imaginez que vous devez entrer dans une cour :
1. Addition par catégories (en parallèle): Il y a $m$ portes à gauche et $n$ portes à droite. Vous n’avez qu’à en choisir une pour entrer. Nombre de méthodes : $m+n$.
2. Multiplication par étapes (en série): Vous devez traverser deux murs. Le premier mur comporte $m$ portes, le deuxième $n$ portes. Vous devez franchir les deux étapes consécutivement. Nombre de méthodes : $m \times n$.
Définition fondamentale des principes de dénombrement
Principe de dénombrement par addition par catégories: Pour les problèmes de classification, chaque catégorie permet de terminer la tâche indépendamment. Son cœur repose sur l'union disjointe des ensembles : $N = m_1 + m_2 + \dots + m_n$.
Principe de dénombrement par multiplication par étapes: Pour les problèmes par étapes, les étapes sont interdépendantes et toutes doivent être accomplies pour finaliser la tâche. Son cœur est le produit cartésien des chemins : $N = m_1 \times m_2 \times \dots \times m_n$.
La classification met l'accent sur l'indépendance et la complétude ; la séquence insiste sur l'interdépendance et la continuité.
Classification indépendante $\implies \sum n_i$
Étapes continues $\implies \prod m_i$
Étapes continues $\implies \prod m_i$